- Title
- Augmented intuition: a bridge between theory and practice
- Creator
- Moscato, Pablo; Mathieson, Luke; Haque, Mohammad Nazmul
- Relation
- ARC.DP120102576 http://purl.org/au-research/grants/arc/DP120102576 | ARC|DP140104183 http://purl.org/au-research/grants/arc/DP140104183 | ARC|DP200102364 http://purl.org/au-research/grants/arc/DP200102364
- Relation
- Journal of Heuristics Vol. 27, Issue 4, p. 497-547
- Publisher Link
- http://dx.doi.org/10.1007/s10732-020-09465-7
- Publisher
- Springer
- Resource Type
- journal article
- Date
- 2021
- Description
- Motivated by the celebrated paper of Hooker (J Heuristics 1(1): 33–42, 1995) published in the first issue of this journal, and by the relative lack of progress of both approximation algorithms and fixed-parameter algorithms for the classical decision and optimization problems related to covering edges by vertices, we aimed at developing an approach centered in augmenting our intuition about what is indeed needed. We present a case study of a novel design methodology by which algorithm weaknesses will be identified by computer-based and fixed-parameter tractable algorithmic challenges on their performance. Comprehensive benchmarkings on all instances of small size then become an integral part of the design process. Subsequent analyses of cases where human intuition “fails”, supported by computational testing, will then lead to the development of new methods by avoiding the traps of relying only on human perspicacity and ultimately will improve the quality of the results. Consequently, the computer-aided design process is seen as a tool to augment human intuition. It aims at accelerating and foster theory development in areas such as graph theory and combinatorial optimization since some safe reduction rules for pre-processing can be mathematically proved via theorems. This approach can also lead to the generation of new interesting heuristics. We test our ideas with a fundamental problem in graph theory that has attracted the attention of many researchers over decades, but for which seems it seems to be that a certain stagnation has occurred. The lessons learned are certainly beneficial, suggesting that we can bridge the increasing gap between theory and practice by a more concerted approach that would fuel human imagination from a data-driven discovery perspective.
- Subject
- algorithms; augmented intelligence; heuristics; human–computer data-driven discovery; kernelization; vertex cover
- Identifier
- http://hdl.handle.net/1959.13/1448955
- Identifier
- uon:43528
- Identifier
- ISSN:1381-1231
- Rights
- This version of the article has been accepted for publication, after peer review (when applicable) and is subject to Springer Nature’s AM terms of use, but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/s10732-020-09465-7
- Language
- eng
- Full Text
- Reviewed
- Hits: 995
- Visitors: 1091
- Downloads: 137
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Author final version | 757 KB | Adobe Acrobat PDF | View Details Download |